// https://leetcode.cn/problems/n-queens-ii/?envType=study-plan-v2&envId=top-interview-150

// 算法思路总结：
// 1. 使用深度优先搜索回溯解决N皇后问题
// 2. 使用三个布尔数组标记列和两个对角线是否被占用
// 3. 对角线索引计算：主对角线i-row+n，副对角线i+row
// 4. 逐行放置皇后，确保行列对角线无冲突
// 5. 时间复杂度：O(N!)，空间复杂度：O(N)

#include <iostream>
using namespace std;

#include <vector>
#include <algorithm>
#include <cstring>

class Solution 
{
private:
    int ret;
    int n;
    bool visCol[10], visDig1[20], visDig2[20];
private:
    void dfs(int row)
    {
        if (row == n)
        {
            ret++;
            return ;
        }

        for (int i = 0 ; i < n ; i++)
        {
            if (!visCol[i] && !visDig1[i - row + n] && !visDig2[i + row])
            {
                visCol[i] = true;
                visDig1[i - row + n] = true;
                visDig2[i + row] = true;

                dfs(row + 1);

                visCol[i] = false;
                visDig1[i - row + n] = false;
                visDig2[i + row] = false;
            }
        }

        return ;
    }
public:
    int totalNQueens(int _n) 
    {
        n = _n, ret = 0;

        memset(visCol, 0, sizeof(visCol));
        memset(visDig1, 0, sizeof(visDig1));
        memset(visDig2, 0, sizeof(visDig2));

        dfs(0);

        return ret;
    }
};

int main()
{
    int n1 = 4, n2 = 1;
    Solution sol;

    cout << sol.totalNQueens(n1) << endl;
    cout << sol.totalNQueens(n2) << endl;

    return 0;
}